\subsection{关于粒球的算法}

\subsubsection{最近邻}
在定义 \ref{def:pointandball} 中, 我们定义了点和粒球的距离, 所以我们就可以实现一下最近邻算法, 最近邻算法就找到点附近的1个最近的粒球, 看其分类即可, 算法 \ref{al:gbknn} 写出了最近邻的过程.
\input{algorithm/GBknn.tex}


\subsubsection{支持向量机}

支持向量机的原始形式:

$$ \begin{aligned}
    & \min \frac{1}{2}\fan{w}^2+C\sum_{i=1}^l\xi_i \\ 
    & \mathrm{s.t. } y_i((w\cdot x_i) + b) \ge 1- \xi_i , \\ 
    & \xi_i \geq 0, i=1,2,\cdots l.
\end{aligned} $$

其中 $\xi_i$ 是松弛变量, $\sum_{i=1}^l\xi_i$ 表示异常值存在的惩罚项.

接下来是可分离形式的粒球 svm:

支持平面 $l_1,l_2$ 可以表示为 
\begin{align}
    l_1: &  w\cdot x + b = 1 \\ 
    l_2: &  w\cdot x + b = -1
\end{align}

\begin{figure}[hbpt]
    \centering
    \caption{可分离形式的粒球支持向量机}
    \includegraphics[width=\linewidth]{figures/GBsvm.png}
    \label{fig:spesvm}
\end{figure}

所以就是 
$$ y_i(w\cdot x+ b) = 1 $$
即 
$$ w\cdot x = y_i - b $$
第一条规则是:从粒球中心 $c_i$ 到支撑平面的垂直距离等于相应的粒球半径$r_i$，其可以由下式描述：
$$ \frac{(c_i-x)w}{\fan{w}}=r_i $$
结合以上可得到 
$$ \frac{c_iw-y_i+b}{\fan{w}}=r_i $$
即 
$$ wc_i-\fan{w}r_i+b=y_i \text{ or } y_i(wc_i-\fan{w}r_i+b) = 1 $$

第二条规则是两个支持平面之间不应该存在中心点, 并且两个平面之间的余量应该尽可能达到最大值.
由于粒球的中心位于支持平面外, 第一条规则的前半部分表示如下
$$ y_i(wc_i\fan{w}r_i+b)>1 $$

用 margin 表示支持平面之间的距离 $d$:
$$ Margin =(x_1-x_2)\cdot w/\fan{w} $$
即 
$$ Margin = 2/\fan{w} $$
所以第二条规则就是
$$ \max 2/\fan{w} $$
等价于 
$$ \min \fan{w}^2/2 $$

所以最后就是一个规划问题:
$$ \begin{aligned}
    & \min \frac{1}{2}\fan{w}^2 \\ 
    & \mathrm{s.t.  } y_i(wc_i-\fan{w}r_i+b)>1, (i=1,2,\cdots)
\end{aligned} $$


